#include <iostream>
#include <string>
#include <vector>
using namespace std;
class Solution {
public:
    int massage(vector<int>& nums) 
    {
        int n=nums.size();
        if(n==0)//判断是否为空
            return 0;
        vector<int> f(n);//创建dp表
        vector<int> g(n);
        g[0]=0;
        f[0]=nums[0];
        for(int i=1;i<n;i++)
        {
            f[i]=g[i-1]+nums[i];//状态转移方程
            g[i]=max(g[i-1],f[i-1]);//状态转移方程
        }
        return max(g[n-1],f[n-1]);//返回值
    }
    //打家劫舍two
    int rob(vector<int>& nums) 
    {
        int n=nums.size();
        if(n==0||n==1||n==2)
        {
            if(n==0) return 0;
            else if(n==1) return nums[0];
            else return max(nums[0],nums[1]);
        }
        return max(nums[0]+_rob(nums,2,n-2),_rob(nums,1,n-1));
    }
    int _rob(vector<int>& nums,int left,int right)
    {
        int n=nums.size();
        vector<int> f(n);
        auto g=f;
        f[left]=nums[left];
        for(int i=left+1;i<=right;i++)
        {
            f[i]=g[i-1]+nums[i];
            g[i]=max(f[i-1],g[i-1]);
        }
        return max(f[right],g[right]);
    }
};
int main()
{
 // cout<<"Hello word";
 int arr[] = { 1,2,3,1 };
    vector<int> nums(arr, arr + 4);
    cout<<Solution().rob(nums)<<endl;
  return 0;
}
